package offerbook;

import java.util.LinkedList;
import java.util.List;

/**
 * 0,1,2,..n-1个数字排成一个圆圈，从0开始每次从这
 * 个圆圈中删除第m个数字，求这个圆圈中剩下的最后一个数字。
 * <p>
 * 方式1：看成是一个链表，遍历。 算法时间复杂度O(mn),空间O(n)
 * <p>
 * 方式2：利用数学分析递归，见笔记详解
 */
public class Code45_LastRemainingNode {

    /**
     * 方式1：利用List模拟。时间O(mn),空间O(n)
     */
    public static int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) return -1;
        if (n == 1) return 0;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int start = 0;
        while (list.size() > 1) {
            int t = start + m - 1;// m = 1代表 0号
            //一直在转圈，超过则取余数
            if (t >= list.size()) {
                t = t % list.size();
            }
            //找到目标target位置，譬如是5
            //移除第5号，然后从第5号重新计算
            list.remove(t);
            start = t;
        }
        return list.get(0);
    }
    /**
     * 方式2：利用HashSet, 思路不对。譬如set含有0，1，2
     * m = 2。那么第一次移除1，还剩0，2.
     * 第二次还是移除1，但是set中没有1，死循环。
     */

    /**
     * 方式3：
     *          0                 n =1
     * f(n,m)=
     *          (f(n-1,m)+m)%n    n>=2
     */
    public static int LastRemaining_Solution3(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        int last = 0; // n = 1
        //当n = 1,不走循环，直接退出 last = 0
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }
    public static void main(String[] args) {
        System.out.println(LastRemaining_Solution(3, 1));
        System.out.println(LastRemaining_Solution3(3, 1));
    }
}

